/*
题目:二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
https://leetcode.cn/problems/diameter-of-binary-tree/
*/
public class DiameterOfBinaryTree {
    int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        pathHeight(root);
        return res;
    }

    //求树的高度
    private int pathHeight(TreeNode root) {
        if (root == null) {
            return 0; //-1表示高度从0开始计算
        }
        int leftHeight = pathHeight(root.left);
        int rightHeight = pathHeight(root.right);

        res = Math.max(res, leftHeight + rightHeight);

        return Math.max(leftHeight, rightHeight) + 1;
    }
}
